"""
寻找第K大
https://www.nowcoder.com/questionTerminal/e016ad9b7f0b45048c58a9f27ba618bf
https://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf?tab=note
有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。
给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。

示例1 输入 [1,3,5,2,2],5,3 输出 2
示例2 输入 [10,10,9,9,8,7,5,6,4,3,4,2],12,3  输出 9
说明 去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9
"""


# -*- coding:utf-8 -*-

class Solution:
    def findKth(self, a, n, K):
        # write code here
        def quickSort(left, right):
            i, j = left, right
            while i < j:
                while i < j and a[j] <= a[left]:
                    j -= 1
                while i < j and a[i] >= a[left]:
                    i += 1
                a[i], a[j] = a[j], a[i]
            a[i], a[left] = a[left], a[i]
            if i < K - 1:
                return quickSort(i + 1, right)
            elif i > K - 1:
                return quickSort(left, i - 1)
            else:
                return a[K - 1]

        return quickSort(0, n - 1)


class Solution1:
    def findKth(self, a, n, K):
        # write code here
        def quickSort(left, right):
            i, j = left, right
            while i < j:
                while i < j and a[j] <= a[left]:
                    j -= 1
                while i < j and a[i] >= a[left]:
                    i += 1
                a[i], a[j] = a[j], a[i]
            a[i], a[left] = a[left], a[i]

            if K - 1 > i:
                return quickSort(i + 1, right)
            elif K - 1 < i:
                return quickSort(left, i - 1)
            else:
                return a[i]

        return quickSort(0, n - 1)


if __name__ == "__main__":
    # arr, n, k = [1, 2, 3, 30, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 37, 25, 26, 27,
    #              28, 29, 4, 31, 32, 33, 34, 35, 36, 24, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49], 49, 24
    # arr, n, k = [1332802, 1177178, 1514891, 871248, 753214, 123866, 1615405, 328656, 1540395, 968891, 1884022, 252932,
    #              1034406, 1455178, 821713, 486232, 860175, 1896237, 852300, 566715, 1285209, 1845742, 883142, 259266,
    #              520911, 1844960, 218188, 1528217, 332380, 261485, 1111670, 16920, 1249664, 1199799, 1959818, 1546744,
    #              1904944, 51047, 1176397, 190970, 48715, 349690, 673887, 1648782, 1010556, 1165786, 937247, 986578,
    #              798663], 49, 24
    # arr1, n, k = [1332802, 1177178, 1514891, 871248, 753214, 123866, 1615405, 328656, 1540395, 968891, 1884022, 252932,
    #               1034406, 1455178, 821713, 486232, 860175, 1896237, 852300, 566715, 1285209, 1845742, 883142, 259266,
    #               520911, 1844960, 218188, 1528217, 332380, 261485, 1111670, 16920, 1249664, 1199799, 1959818, 1546744,
    #               1904944, 51047, 1176397, 190970, 48715, 349690, 673887, 1648782, 1010556, 1165786, 937247, 986578,
    #               798663], 49, 24
    # arr2, n, k = [1332802, 1177178, 1514891, 871248, 753214, 123866, 1615405, 328656, 1540395, 968891, 1884022, 252932,
    #               1034406, 1455178, 821713, 486232, 860175, 1896237, 852300, 566715, 1285209, 1845742, 883142, 259266,
    #               520911, 1844960, 218188, 1528217, 332380, 261485, 1111670, 16920, 1249664, 1199799, 1959818, 1546744,
    #               1904944, 51047, 1176397, 190970, 48715, 349690, 673887, 1648782, 1010556, 1165786, 937247, 986578,
    #               798663], 49, 24
    # arr3, n, k = [1, 3, 5, 2, 2], 5, 3
    arr3, n, k = [1, 10, 5, 6, 8, 7, 5, 6], 8, 3
    A = Solution()
    print(A.findKth(arr3, n, k))
    A = Solution1()
    print(A.findKth(arr3, n, k))
